#include <iostream>
/*
    和单链表类似 
    双链表的基础节点也是需要有 数据
    但是区别在有 prev 先前的节点和
    next 节点 
*/
class Node{
public: 

/*
    构造函数 给数据赋值 同时给两个指针置为0
*/
    Node(int data);
};


/*
    双链表的类 
    存在头结点和尾部节点 以及 整个表的长度
*/
class DoublyLinkedList{
private:

public:
/*
    构造函数 进行初始化即可 初始置为0
*/
    DoublyLinkedList();

/*
    析构函数 首先使用当前节点和next节点 （两位大能）
    可以理解成通过遍历这件事来删除每一个节点。
    具体过程就是 先把 next 节点移动为 当前节点的下一个节点 
    然后删除掉当前节点 让 当前节点成为下一个节点 
    最后出循环把头结点和 尾节点置空 

*/
    ~DoublyLinkedList();

    //是否为空 依旧是头结点是否为空
    bool isEmpty();

    // 获取长度 直接返回链表的长度即可 
    int getSize();

    /*
        头插法 
        首先判断是否为空链表
        空  就直接头尾都指向新节点 返回即可
        不空  那就让新节点的下一个节点为头结点
              头结点的前一个节点是 新节点 
              然后 新节点成为新的头结点。
        最后 增加长度即可
    */
   void insertAtHead(int data);


   /*
        尾插法 
        还是先要判断是否为空链表 
        空 就直接让头尾指向新节点  返回
        不空 就让尾部的下一个节点 成为新节点 
            让旧尾巴成为新节点的前一个节点
            然后新节点成为新的尾巴 
        最后增加长度 
   */
    void insertAtTail(int data);

    /*
        在任意位置插入 
        首先 判断位置这件事 是否合理 
            即 如果位置<0 或者 位置超过了长度 
            提示返回即可 
        如果 Position为 0 那就头插法 返回 
        如果 Position 为 size-1 使用尾插法 返回 
        创建新节点 
        常规情况 这里要看是 临近头结点还是尾节点 
        如果 Position 比较靠近头部 那选择从头部进行遍历 
        使用一个current 节点从头结点开始 
        如果 size < position  就 继续往下移动 
        找到位置，那么就让新节点的上一个节点  是 当前节点上一个节点
                新节点的下一个节点是当前节点 
                当前节点的先前节点的下一个节点就是新节点 
        如果 靠近尾部  会选择从尾部进行遍历 
        使用 current = tail  从size -1 的位置开始遍历 
        这次时从后往前 应该是递减的顺序进行 > position 为止就好 
        然后不断把current 往前移动 = current-> prev 
        找到之后  就是 新节点的先前节点 = current 的先前节点 
                    新节点的下一个节点 = current 
                    当前节点的先前的下一个 = 新节点 
                    当前节点的前一个 = 新节点 
        最后 记得增加长度 
    */
   void insertAtPosition(int data);


    /*
        首先还是要判断是否为空 如果空 提示无法删除直接返回
        不空 要继续讨论情况 
        首先创建一个temp 节点把头暂时存起来 
        1、 头尾指针重合 也就是链表当中只有一个元素的情况下
            那直接头尾指针置为空即可 
        2. 不重合的情况下 头 = 头的下一个 
            头的前一个置为空 
            然后删掉 temp 
            长度减少1 
    */
    void deleteHead();


    /*
        判断是否为空 
        头尾是否重合  这两种都同上 
        不重合的情况下 
            尾指针前移  
            同时 尾指针的下一个置为空
        删掉temp 
        长度减1

    */
    void deleteTail();

    /*
        删除指定位置，跟插入指定位置的很像 
        大体思路都比较类似，把插入换成删除操作 
        这里一般是 用position <= size/2来判断头尾  
        1. 位置是否合法 
        2. 删头部还是删尾部 两个特殊情况特判返回 
        3. 使用current 进行遍历 一般情况
            1)距离头比较近 就从头开始遍历 知道 < position为止
            2)离尾指针比较近 从尾部开始遍历 直到 >position 
        4. 当前节点的前面的下一个 是当前节点的下一个 
           当前节点的下一个的先前的 是 当前节点的先前的
           删除当前节点  长度减1
    */
    void deleteAtPosition(int position);


    /*
        1. 是否空 无法提示 返回 
        2. 判断头尾是否满足 直接头删 或者删尾部 然后返回 
        一般情况  从 当前节点 给到头结点的next 节点开始遍历 
        当 当前节点不空 且 当前节点不在尾部
        如果 当前节点是我要删除的数据 
            当前节点的先前节点的下一个节点 = 当前节点的下一个节点
            当前节点的后一个节点的先前节点 = 当前节点的先前节点 
            删除 当前节点
            长度减 1  返回即可 
        把当前节点后移   
        没找到要删除的元素 就直接输出 无法删除   
    */
    void deleteNode(int data);

    /*
        查找函数跟单链表完全一致 
        判断空不空  false 
        不空就开始遍历 找 
        找到返回 true  
        找不到 false 
    */
    bool search(int data);  


    /*
        空 就提示无法遍历  返回
        头结点不空 current 就进行遍历
        输出节点的数据 当前节点的下一个不空  就 <->
        否则 ->  继续移动即可  
    */
    void displayforward();

    /*
        反转遍历 
        其实就是把上面的头结点换成从尾部开始 
        所有的 next 换成 prev 即可 
        加换行 和 null 
    */
    void displayReverse();

};


int main(){
    
}